๋ฌธ์
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฒญ์ํ๋ ์์ญ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์ฅ์๋ NรM ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, 1ร1ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ๋ฒฝ ๋๋ ๋น ์นธ์ด๋ค. ์ฒญ์๊ธฐ๋ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด ์์ผ๋ฉฐ, ์ด ๋ฐฉํฅ์ ๋, ์, ๋จ, ๋ถ์ค ํ๋์ด๋ค. ์ง๋์ ๊ฐ ์นธ์ (r, c)๋ก ๋ํ๋ผ ์ ์๊ณ , r์ ๋ถ์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์, c๋ ์์ชฝ์ผ๋ก ๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์์ด๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ํ๋ค.
- ํ์ฌ ์์น๋ฅผ ์ฒญ์ํ๋ค.
- ํ์ฌ ์์น์์ ํ์ฌ ๋ฐฉํฅ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ ๋ฐฉํฅ๋ถํฐ ์ฐจ๋ก๋๋ก ์ธ์ ํ ์นธ์ ํ์ํ๋ค. a. ์ผ์ชฝ ๋ฐฉํฅ์ ์์ง ์ฒญ์ํ์ง ์์ ๊ณต๊ฐ์ด ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ํ ์นธ์ ์ ์งํ๊ณ 1๋ฒ๋ถํฐ ์งํํ๋ค. b. ์ผ์ชฝ ๋ฐฉํฅ์ ์ฒญ์ํ ๊ณต๊ฐ์ด ์๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ๊ณ 2๋ฒ์ผ๋ก ๋์๊ฐ๋ค. c. ๋ค ๋ฐฉํฅ ๋ชจ๋ ์ฒญ์๊ฐ ์ด๋ฏธ ๋์ด์๊ฑฐ๋ ๋ฒฝ์ธ ๊ฒฝ์ฐ์๋, ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ ์ ์งํ ์ฑ๋ก ํ ์นธ ํ์ง์ ํ๊ณ 2๋ฒ์ผ๋ก ๋์๊ฐ๋ค. d. ๋ค ๋ฐฉํฅ ๋ชจ๋ ์ฒญ์๊ฐ ์ด๋ฏธ ๋์ด์๊ฑฐ๋ ๋ฒฝ์ด๋ฉด์, ๋ค์ชฝ ๋ฐฉํฅ์ด ๋ฒฝ์ด๋ผ ํ์ง๋ ํ ์ ์๋ ๊ฒฝ์ฐ์๋ ์๋์ ๋ฉ์ถ๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๋ ์ด๋ฏธ ์ฒญ์๋์ด์๋ ์นธ์ ๋ ์ฒญ์ํ์ง ์์ผ๋ฉฐ, ๋ฒฝ์ ํต๊ณผํ ์ ์๋ค.
์ , ์ถ๋ ฅ
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (3 โค N, M โค 50)
- ๋์งธ ์ค์ ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์นธ์ ์ขํ (r, c)์ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ d๊ฐ ์ฃผ์ด์ง๋ค. d๊ฐ 0์ธ ๊ฒฝ์ฐ์๋ ๋ถ์ชฝ์, 1์ธ ๊ฒฝ์ฐ์๋ ๋์ชฝ์, 2์ธ ๊ฒฝ์ฐ์๋ ๋จ์ชฝ์, 3์ธ ๊ฒฝ์ฐ์๋ ์์ชฝ์ ๋ฐ๋ผ๋ณด๊ณ ์๋ ๊ฒ์ด๋ค.
- ์ ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ฅ์์ ์ํ๊ฐ ๋ถ์ชฝ๋ถํฐ ๋จ์ชฝ ์์๋๋ก, ๊ฐ ์ค์ ์์ชฝ๋ถํฐ ๋์ชฝ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋น ์นธ์ 0, ๋ฒฝ์ 1๋ก ์ฃผ์ด์ง๋ค. ์ง๋์ ์ฒซ ํ, ๋ง์ง๋ง ํ, ์ฒซ ์ด, ๋ง์ง๋ง ์ด์ ์๋ ๋ชจ๋ ์นธ์ ๋ฒฝ์ด๋ค.
- ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์นธ์ ์ํ๋ ํญ์ ๋น ์นธ์ด๋ค.
์ถ๋ ฅ
- ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฒญ์ํ๋ ์นธ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ Logic
class Robot {
int x;
int y;
int dir;
public Robot(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
}
- ๋ก๋ด ์ฒญ์๊ธฐ์ ์์น๋ฅผ ์ ์ฅํ๋ ํด๋์ค
public int cleanRoom(int r, int c, int d) {
int cleanCount = 0;
queue.add(new Robot(r, c, d));
while(!queue.isEmpty()) {
Robot robot = queue.poll();
if (map[robot.x][robot.y] == 0) {
map[robot.x][robot.y] = 2;
cleanCount++;
}
if (!checkWallMethod(robot)) {
moveBack(robot);
}
}
return cleanCount;
}
- ๋ฌธ์ ์์ ์ฃผ์ด์ง ์๋ ๋ก์ง์ ๊ตฌํํ ๋ฉ์๋
- Queue๋ฅผ ์ด์ฉํ BFS๋ฐฉ์์ผ๋ก ์ฒญ์ํ ์์ญ์ ํ์ํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.*;
import java.util.*;
class Robot {
int x;
int y;
int dir;
public Robot(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
}
class Directions {
int x;
int y;
public Directions(int x, int y) {
this.x = x;
this.y = y;
}
}
class Room {
int[][] map;
int N, M;
Queue<Robot> queue = new LinkedList<>();
Directions[] directions = {new Directions(-1, 0), new Directions(0, 1), new Directions(1, 0), new Directions(0, -1)};
public Room (int n, int m) {
N = n;
M = m;
map = new int[n][m];
}
public int cleanRoom(int r, int c, int d) {
int cleanCount = 0;
queue.add(new Robot(r, c, d));
while(!queue.isEmpty()) {
Robot robot = queue.poll();
if (map[robot.x][robot.y] == 0) {
map[robot.x][robot.y] = 2;
cleanCount++;
}
if (!checkWallMethod(robot)) {
moveBack(robot);
}
}
return cleanCount;
}
private void moveBack(Robot robot) {
int backDir = turnBack(robot.dir);
int backX = robot.x + directions[backDir].x;
int backY = robot.y + directions[backDir].y;
if (!checkBoundary(backX, backY)) {
if (map[backX][backY] != 1) {
queue.add(new Robot(backX, backY, robot.dir));
}
}
}
private boolean checkWallMethod(Robot robot) {
for (int i = 0; i < 4; i++) {
int nextDir = turnLeft(robot.dir);
int nextX = robot.x + directions[nextDir].x;
int nextY = robot.y + directions[nextDir].y;
robot.dir = nextDir;
if (checkBoundary(nextX, nextY)) continue;
if (map[nextX][nextY] == 0) {
queue.add(new Robot(nextX, nextY, nextDir));
return true;
}
}
return false;
}
private boolean checkBoundary(int r, int c) {
return r < 0 || r >= N || c < 0 || c >= M;
}
private int turnLeft(int d) {
return (d + 3) % 4;
}
private int turnBack(int d) {
return (d + 2) % 4;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int M = Integer.parseInt(line[1]);
Room room = new Room(N, M);
line = br.readLine().split(" ");
int r = Integer.parseInt(line[0]);
int c = Integer.parseInt(line[1]);
int d = Integer.parseInt(line[2]);
for (int i = 0; i < N; i++) room.map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(room.cleanRoom(r, c, d));
br.close();
}
}
โ๏ธ Review
- ์๋ฎฌ๋ ์ด์ ๋ฌธ์ ๋ ์ฃผ์ด์ง ์กฐ๊ฑด์ ๋ฐ๋ผ ๋ก์ง์ ๊ตฌํํ๋ ๋ฐฉ์์ผ๋ก ์ดํดํด, ๋ก๋ด์ฒญ์๊ธฐ์ ์๋์๋ฆฌ๋ง๋ค์ ๋ฉ์๋๋ฅผ ๊ตฌํํ๋ ค ํ๋ค.
- ์ต๋ํ ๊ฐ์ฒด ์งํฅ์ ์ผ๋ก ๋ค์ฌ์ฐ๊ธฐ ํ์๋ ๊ณ ๋ คํ๋ฉด์ ๋ฉ์๋ ์ถ์ถ์ ์ํํ๋ค.
๐ ์ถ์ฒ
Baekjoon : https://www.acmicpc.net/problem/14503